Preorders

Preorders are just equivalence relations without the symmetric condition.
Every set can be considered as a discrete preorder with the binary relation of equality. Also the trivial opposite (codiscrete preorder) where all pairs are in the relation.
Every graph yields a preorder on the vertices where \(v \leq w\) iff there is a path from \(v\) to \(w\).
- Reflexive because of length-0 paths, transitive because of path concatenation.
Product of two preorders can be considered as a preorder by only comparing things when both preorders independently agree on the pairs.

Preorder(1)

A preorder / partial order / total order relation on a set \(X\)

Preorder: a binary relation on \(X\) that is reflexive and transitive.
A partial order (poset) has the additional constraint that \(x \leq y \land y \leq x \implies x=y\)
- We can always get a partial order from a preorder by quotienting, so it’s not that special.
A total order has all elements comparable.

Linked by

Exercise 1-53(2)

For any set \(S\) there is a coarsest partition having just one part.

What surjective function does this correspond to?

(Likewise for the finest partition?)

Solution(1)

The trivial map to \(\{1\}\) and the identity, respectively.

Exercise 1-55(2)

Prove that the upper sets on a discrete preorder for some set \(X\) is simply the power set \(P(X)\)

Solution(1)

The upper set criterion is satisfied by any subset, thus all possible subsets are upper sets.
The binary relation is equality, thus the upper subset criterion becomes \(p \in U \land p = q \implies q \in U\) or alternatively \(p \in U \implies p \in U\) which is always satisfied.

Graph(1)

A graph (of vertices, arrows)

A tuple \(G=(V, A, s, t)\)
Set of vertices and arrows, with two functions \(A\rightarrow V\) which say where the source and target of each arrow goes to.
A path in \(G\) is any sequence of arrows such that the target of one arrow is the source of the next (including length 0 and 1 sequences).

Linked by

Free category on a graph: referenced

Opposite preorder(1)

An opposite preorder

Given a preorder \((P, \leq)\), we define \(p \leq^{op} q \iff q \leq p\)

Linked by

Skeletality(1)

Categorical skeletality generally means \(x \cong y \implies x = y\)

E.g. a skeletal preorder is a poset.

Linked by

Upper set(1)

An upper set in \(P\) for some preorder \((P, \leq)\)

A subset \(U\) of \(P\) satisfying the condition \(p \in U \land p \leq q \implies q \in U\)
Anything you add to the upper set means you have to add everything greater than it.
Example: the possible upper sets of \(Bool\) are \(\{\varnothing, \{true\}, \{true, false\}\}\)

Linked by